package may.test_5_17;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    public int maxTurbulenceSize(int[] arr) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = arr.length;
        int[] f = new int[n];
        int[] g = new int[n];
        for(int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
        }
        int ret = 1;
        for(int i = 1; i < n; i++) {
            if(arr[i - 1] < arr[i]) {
                f[i] = g[i - 1] + 1;
            } else if(arr[i - 1] > arr[i]) {
                g[i] = f[i - 1] + 1;
            }
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }
        return ret;
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        // 优化⼀：将字典⾥⾯的单词存在哈希表⾥⾯
        Set<String> hash = new HashSet(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // 初始化，保证我们后续填表是正确的
        s = " " + s; // 处理下标的映射关系
        for(int i = 1; i <= n; i++) {
            // 填 dp[i]
            for(int j = i; j >= 1; j--) {
                //最后⼀个单词的起始位置
                if(dp[j - 1] && hash.contains(s.substring(j, i + 1))) {
                    dp[i] = true;
                    break; // 优化⼆
                }
            }
        }
        return dp[n];
    }
    public int findSubstringInWraproundString(String ss) {
        int n = ss.length();
        char[] s = ss.toCharArray();
        // 1. 利⽤ dp 得到每⼀个位置为结尾的最⻓连续数组的⻓度
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for(int i = 1; i < n; i++) {
            if (s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a')) {
                dp[i] += dp[i - 1];
            }
        }
        // 2. 去重
        int[] hash = new int[26];
        for (int i = 0; i < n; i++) {
            hash[s[i] - 'a'] = Math.max(hash[s[i] - 'a'], dp[i]);
        }
        // 3. 返回结果
        int sum = 0;
        for(int x : hash) {
            sum += x;
        }
        return sum;
    }
}
